package 链表;

import java.util.*;
import java.util.jar.JarEntry;

public class Solution12 {
    //https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024
    public ListNode deleteDuplicates1 (ListNode head) {
        //思路1：栈维护
        Stack<ListNode> stack = new Stack<>();
//        stack.get(0);//实现List接口，也是链式的可以指定下标获取（ArrayList），栈底元素
//        stack.peek();//为空会抛异常
        ListNode cur = head;
        while (cur != null) {
            if(stack.isEmpty()) {
                stack.push(cur);
                cur = cur.next;
            }else {
                if(stack.peek().val == cur.val) {
                    int count = stack.pop().val;
                    if(!stack.isEmpty()) {
                        stack.peek().next = null;
                    }
                    while (cur != null && cur.val == count) {
                        cur = cur.next;
                    }
                }else {
                    stack.peek().next = cur;
                    stack.push(cur);
                    cur = cur.next;
                }
            }
        }
        if(stack.isEmpty()) {
            return null;
        }
        return stack.get(0);
    }
    //思路2：双指针rear、prev遍历探寻
    public static ListNode deleteDuplicates2 (ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        ListNode reHead = null;
        ListNode tail = reHead;

        ListNode prev = head;
        ListNode rear = head.next;
        while (rear != null) {
            if(rear.val != prev.val) {
                if(reHead == null) {
                    reHead = prev;
                    tail = reHead;
                }else {
                    tail.next = prev;
                    tail = tail.next;
                }
                prev = rear;
                rear = rear.next;
            }else {
                while (rear != null && rear.val == prev.val) {
                    rear = rear.next;
                }
                prev = rear;
                if(rear != null) {
                    if(reHead == null && (rear.next == null || rear.val != rear.next.val)) {
                        reHead = rear;
                        tail = rear;
                    }
                    rear = rear.next;
                }
                if(rear == null) {
                    if(reHead != null && reHead != prev) {
                        tail.next = prev;
                    }
                }
            }
        }
        return reHead;
    }
    //思路3：用Map键装Integer(重写实现了equals方法)，值装出现次数，会去重Integer
    //遍历原链表，用它里面的值判断此节点存在次数，虽然用Integer，但能获得当前遍历的节点
    public static ListNode deleteDuplicates3 (ListNode head) {
        Map<Integer,Integer> map = new HashMap<>();
        ListNode cur = head;
        while (cur != null) {     //设置键的值
            map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);
            cur = cur.next;
        }
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        cur = head;
        while (cur != null) {
            if(map.get(cur.val) == 1) {
                tail.next = cur;
                tail = tail.next;
            }
            cur = cur.next;
        }
        tail.next = null;
        return dummy.next;
    }
    public static ListNode deleteDuplicates (ListNode head) {
        //题解
        //思路：三指针，中遍历与前后判断
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;
        //第一个节点的判断处理
        if(head.val != head.next.val) {
            tail.next = head;
            tail = tail.next;
        }
        ListNode prev = head;
        ListNode mid = head.next;
        ListNode late = mid.next;
        while (late != null) {
            if(mid.val != prev.val && mid.val != late.val) {
                tail.next = mid;
                tail = tail.next;
            }
            prev = prev.next;
            mid = mid.next;
            late = late.next;
        }
        //最后一个节点的判断处理
        if(mid.val != prev.val) {
            tail.next = mid;
            tail = tail.next;
        }
        tail.next = null;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(2);
        ListNode node6 = new ListNode(3);
        ListNode node7 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        ListNode node = deleteDuplicates2(node1);
    }
}
